#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>

/**
 * Luogu P1194: Buying Gift
 * The solution is easy, but modeling the problem as Minimal Spanning Tree is
 * not so easy.
 */

std::vector<int> root;

int find(int i) {
    if (i != root[i]) root[i] = find(root[i]);
    return root[i];
}

void union_(int i, int j) {
    int r1 = find(i), r2 = find(j);
    root[r2] = r1;
}

struct Edge {
    int u, v;
    int k;

    bool operator>(const Edge &other) const { return k > other.k; }
};

int main() {
    // Input and create heap
    int price, nItems;
    scanf("%d %d", &price, &nItems);
    for (int i = 0; i < nItems; i++) root.push_back(i);
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge> > edges;
    for (int i = 0; i < nItems; i++) {
        for (int j = 0; j < nItems; j++) {
            int k;
            scanf("%d", &k);
            if (i >= j) continue;
            if (k == 0) k = price;
            k = std::min(k, price);
            edges.push({i, j, k});
        }
    }

    // Create minimal spanning tree
    int cost = price;
    while (!edges.empty()) {
        Edge e = edges.top();
        edges.pop();
        if (find(e.u) == find(e.v)) continue;
        union_(e.u, e.v);
        cost += e.k;
    }
    printf("%d\n", cost);

    return 0;
}